package com.njupt.StringProblem;

import java.util.Arrays;

/**
 * 151. 反转字符串中的单词
 */
public class ReverseWords {


    /**
     *
     * 法一：使用库函数中的split函数分割字符串
     * @param s
     * @return
     */
    public String reverseWords(String s) {

        StringBuffer stringBuffer = new StringBuffer();
        s = s.trim();
        String[] s1 = s.split(" ");
        System.out.println(Arrays.toString(s1));
        for (int i = s1.length-1; i>=0; i--) {
            if(s1[i].equals("")){
                continue;
            }
            stringBuffer.append(s1[i]);
            stringBuffer.append(" ");
        }
        return stringBuffer.toString().trim();
    }

    /**
     * 思路二：
     * 1、删除字符串中得多余空格，在原地伤处不采用额外得辅助空间
     * 2、将整个字符串反转
     * 3、在此反转每个单词
     * @param arr
     */
    public void stringReverse(char[] arr){
        int startIndex = 0;
        int endIndex = arr.length-1;
        char temp;
        while(true){
            temp = arr[startIndex];
            arr[startIndex] = arr[endIndex];
            arr[endIndex] = temp;
            startIndex++;
            endIndex--;
            if(startIndex>endIndex){
                break;
            }
        }
    }

    //1、删除多余的空格
        //删除首位空格，以及中间多余空格
    public StringBuilder removeSpace(String s){
        int start = 0;
        int end = s.length()-1;
        while(s.charAt(start) == ' ') start++;
        while(s.charAt(end) == ' ') end--;
        StringBuilder stringBuilder = new StringBuilder();
        char c ;
        while(start<=end){
            c = s.charAt(start);
            // 接近源码的高明写法
            if(c!=' ' || stringBuilder.charAt(stringBuilder.length()-1) !=' '){
                stringBuilder.append(c);
            }
            start++;
        }
        return stringBuilder;


    }

    //2、反转字符串中的每一个单词
    public void reverseEachWord(StringBuilder sb){

        int len = sb.length();
        int start = 0; //找到字符串中，每个单词的开头
        int end = 0;   //找到字符串中，每个单词的结尾
        while(start<len){
            while(end<len && sb.charAt(end)!=' '){
                end++;
            }
            reverseString(sb,start,end-1);
            start = ++end;
        }
    }

    //3、反转字符串中的指定区间中的字符[start,end]
    public void reverseString(StringBuilder sb,int startIndex,int endIndex){
        char temp;
        while(true){
            temp = sb.charAt(startIndex);

            sb.setCharAt(startIndex,sb.charAt(endIndex));
            sb.setCharAt(endIndex,temp);
            startIndex++;
            endIndex--;
            if(startIndex>endIndex){
                break;
            }
        }
    }

    public String reverseWords1(String s) {
        StringBuilder stringBuilder = removeSpace(s);
        reverseString(stringBuilder,0,stringBuilder.length()-1);
        reverseEachWord(stringBuilder);
        return stringBuilder.toString();

    }

    /**
     * 法二得另一种写法,原地溢出多余得空格
     * @param
     * @return
     */
    public char[] removeSpaceByOrin(char[] charArray){
        //删除最前面得空格
        int slowIndex = 0; int fastIndex = 0;
        while (fastIndex<charArray.length && charArray[fastIndex] == ' '){
            fastIndex++;
        }
        for (;fastIndex<charArray.length;fastIndex++){
            if(fastIndex>1
                    &&charArray[fastIndex-1] == charArray[fastIndex]
                    &&charArray[fastIndex] == ' '){
                continue;
            }else {
                charArray[slowIndex++] = charArray[fastIndex];
            }
        }
        //直接在内存中对目标数组直接操作
        char[] newChar = new char[slowIndex];
        System.arraycopy(charArray,0,newChar,0,slowIndex);
        return newChar;
    }

    public char[] stringReverse(char[] charArray,int start,int end){

        int left = start; int right = end;
        while(left<=right){
            char temp = charArray[left];
            charArray[left] = charArray[right];
            charArray[right] = temp;
            left++;
            right--;
        }
        return charArray;
    }

    public String eachStringReverse(char[] charArray){
        int start = 0;
        for (int i = 0; i <= charArray.length; i++) {
            if( i== charArray.length|| charArray[i] ==' '){
                stringReverse(charArray,start,i-1);
                start = i+1;
            }
        }
        return new String(charArray);
    }
    public static void main(String[] args) {

        String s = "a good     example";
        ReverseWords test = new ReverseWords();
////        String s1 = test.reverseWords(s);
////        System.out.println(s1);
//        StringBuilder stringBuilder = test.removeSpace(s);
//        System.out.println(stringBuilder);
//        test.reverseString(stringBuilder,0,stringBuilder.length()-1);
//        test.reverseEachWord(stringBuilder);
//        System.out.println(stringBuilder);
//        System.out.println(test.reverseWords1(s));

        char[] chars = test.removeSpaceByOrin(s.trim().toCharArray());
        char[] chars1 = test.stringReverse(chars, 0, chars.length - 1);
        String string = test.eachStringReverse(chars1);

    }
}
